\section{Background}

\subsection{The Game of Amazons}
The game of Amazons (created by Walter Zamkauskas in 1988, Amazons for short), is a two-player zero-sum game with perfect information. The game is usually played on \mydim{10}{10} board with each player controlling 4 queens (a.k.a. Amazons). The queens, like a \myem{Queen} in Chess, can move any number of empty squares horizontally, vertically or didiagonally but cannot capture the opponent's queens. Each player take turns to move (assume Black goes first in this paper); in each turn, one player moves one of his queens and then shoot an arrow (also travels like a queen) to block an empty square on the board. Neither the queens nor the arrows can travel across another queen or the blocked squares. Players cannot pass, the last player who can make a move wins the game. For example, \refFigure{fig:moveDemo} shows one possible move for Black in the \mydim{6}{6} Amazons starting position.

\begin{figure}[htbp] 
    \centering
    \input{./figures/move_demo}
    \caption{Black queen at $B6$ moves to $B3$ and shoot $E3$}
    \label{fig:moveDemo}
\end{figure}

From a strategic point of vies, Amazons is a territory game where each player is trying to maximizing his mobility (thus minimizing his opponent's) by making and defending territories by moving and shooting. From a computational point of view, Amazons poses a daunting search task because of its high braching factor, high state-complexity (the number of possible unique positions in the search tree) and high search-tree complexity complexity (the number of positions in the search tree). For example, \mydim{10}{10} Amazons is estimated to have a branching factor of, on average, $374$ for Black and $299$ for White, a state complexity of $O(10^{40})$ and a decision complexity of $O(10^{212})$ \cite{hensgens_thesis_2001}. 

\subsection{Partitioning and Solving Amazons}
Since an arrow is shot to block an empty square at each turn, the board usually decomposes in to several independent components towards the end of a game. For example, \refFigure{fig:endgame_partition} shows an endgame position that is partitioned into two independent components delimited by the blue solid lines. An improved partition can be obtained by identifying \myem{blocker} queens whice separate areas that only contains queens of that color \cite{slv_5x5}. For example, the bigger subgame in \refFigure{fig:endgame_partition} can be further partitioned into two components (delimited by red dashed lines) by identifying the White blocker queen $D3$. Notice that the two components both contain this White blocker queen $D3$ and Black cannot access the lower-right component if $D3$ wouldn't move.

\begin{figure}[htbp] 
    \centering
    \input{./figures/endgame_partition}
    \caption{Board partition}
    \label{fig:endgame_partition}
\end{figure}

Areas can be categorized as follows:
\begin{enumerate}
\item A \mybf{Simple Territory} has at least one empty square, queen(s) of one color but no blockers (e.g., the lower left component in \refFigure{fig:endgame_partition} is a Black simple territory);
\item A \mybf{Blocker Territory} has at least one empty square, queen(s) of one color but at least one blocker (e.g., the lower right component in \refFigure{fig:endgame_partition} is a White blocker territory);
\item An \mybf{Active Area} has at least one empty square and at least one queen from each color (the upper right component in \refFigure{fig:endgame_partition} is an active area).
\end{enumerate} 

In order to weakly solve an Amazons game, we only need to know if a player have more moves than his opponent, as Mueller discovered in solving \mydim{5}{5} Amazons \cite{slv_5x5}. To serve this purpose, he computed bounds on the number of black moves minus the number of white moves. Suppose the bounds are \mybounds{m}{n}, then the outcome of the game can be determined as follows: 
\begin{enumerate}
\item \mybf{Black wins} if $m > 0$ (Black can make at least $n$ more moves) or $m = 0$ but White has to move first (Black has at least as many moves and can make the last move);
\item \mybf{White wins} if $n < 0$ or $n = 0$ but Black has to move first;
\item \mybf{Unknown} otherwise.
\end{enumerate}

Partitioning of the board with blockers together with the bounds computation solves \mydim{5}{5} as a first player win \cite{slv_5x5}.

\subsection{Local Databases}
Databases have been vastly used for building both strong game-playing and game-solving programs. For example, endgame databases for solving checkers \cite{checker_solved_2007} and pattern databases are prevalent in Go programs \cite{go_mmuller_2002}. Despite the successful application of these various types of databases, none of them really fit into solving Amazons. The endgame databases used in solving checkers contains full-board endgame positions with up to 10 pieces, however full-board positions are redundant in solving Amazons since the board will be decomposed into individual components. Pattern databases are local but they are used heuristic evaluations and thus not precise enough for solving.

The main application of local databases to Amazons was Tegos' usage of local minimax databases for a strong Amazons player \myem{Antiope} \cite{tegos_thesis_2002}. His databases contains simple territories and active areas with their exact minimax values up to size \mydim{4}{6} for both colors and is considered to have improved \myem{Antiope}'s playing strength drastically (e.g., find out the exact minimax value of a game 23 plys earlier than without the databases). Tegos also computed combinatorial database (up to size \mydim{4}{4} which stores the combinatorial game theoretical values of a game but it is not used in \myem{Antiope} since the minimax databases suffice for a decent player and have more positions available.

